package algorithm.t202110;

import org.omg.CORBA.SetOverrideType;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * @author : 李红磊
 * @version :1.0
 * @date : 2021/10/28 8:47
 * @description :2道
 */
public class t20211028 {


    //重新排列得到2的幂
    public boolean reorderedPowerOf2(int n) {

        String[][] arr = {
                {"1", "2", "4", "8"},//1位数
                {"16", "32", "64"},//2位
                {"128", "256", "512"},//3位数
                {"1024", "2048", "4096", "8192"},//4位10 11 12 13
                {"16384", "32768", "65536"},//14 15 16
                {"131072", "262144", "524288"},//17 18 19
                {"1048576", "2097152", "4194304", "8388608"},//20 21 22 23
                {"16777216", "33554432", "67108864"},//24 25 26
                {"134217728", "268435456", "536870912"}//27 28 29

        };


        String number = String.valueOf(n);//将数字转为字符串

        for (int i = 0; i < arr[number.length() - 1].length; i++) {

            String sort_num = sort(number);//拿到排序后的源字符串

            String target = sort(arr[number.length() - 1][i]);//目标2的幂次字符也是经过排序
            if (target.equals(sort_num)) {//两两比较
                return true;
            }
        }
        return false;

    }

    //字符串排序
    private String sort(String number) {
        char[] chars = number.toCharArray();
        Arrays.sort(chars);
        return new String(chars);
    }

    //438.找到字符串中所有字母异同位
    static public List<Integer> findAnagrams(String s, String p) {
        ArrayList<Integer> res = new ArrayList<>();
        //若s为空但p不为空或者p的长度大于s，都可以说明s不含有p的排列，直接返回
        if (s == null && p != null || p.length() > s.length()) return res;

        //由于题目给定均为小写，这里给定长度26
        int[] arr = new int[26];
        int[] arrP = new int[26];
        for (int i = 0; i < p.length(); i++) {
            arrP[p.charAt(i) - 'a']++;
        }

        int len = p.length();

        int fast = len - 1, slow = 0;//双指针


        for (int i = 0; i < len; i++) {//先将fast之前的元素加入arr
            arr[s.charAt(i) - 'a']++;
        }

        //进行处理
        while (fast < s.length()) {
            if (fast - slow > (len - 1)) {
                arr[s.charAt(slow) - 'a']--;
                slow++;
                arr[s.charAt(fast) - 'a']++;
            }

            if (Arrays.equals(arr, arrP)) {
                res.add(slow);
            }

            fast++;

        }

        return res;
    }

    //713.乘积小于k的子数组
    static public int numSubarrayProductLessThanK(int[] nums, int k) {
        if (nums == null) {
            return 0;
        }

        int fast = 0, slow = 0;

        int count = 0;

        for (; fast < nums.length && slow < nums.length; ) {
            if (fast == slow && nums[fast] < k) {
                count++;
                fast++;
                continue;
            } else if (fast == slow && nums[fast] >= k) {
                fast++;
                slow++;
                continue;

            } else {//程序走到这，说明slow和fast指向的已经不是同一个地方了

                if (slow + 1 == fast) {//判断slow和fast是否相邻着
                    if (nums[slow] * nums[fast] < k) {
                        count++;
                        if (fast + 1 >= nums.length) {
                            slow++;
                            fast = slow;
                            continue;
                        }
                        fast++;
                        continue;
                    } else {
                        slow++;
                        continue;
                    }
                } else {//slow和fast不相邻
                    int tempSum = 1;
                    int number = slow;
                    while (number <= fast) {
                        tempSum = tempSum * nums[number];
                        number++;
                    }
                    if (tempSum < k) {
                        count++;
                        if (fast + 1 >= nums.length) {
                            slow++;
                            fast = slow;
                            continue;
                        }
                        fast++;
                        continue;
                    } else {
                        slow++;
                        fast = slow;
                        continue;
                    }

                }

            }


        }

        return count;
    }

    //209.长度最小的子数组
    static public int minSubArrayLen(int target, int[] nums) {
        if (nums == null || nums.length == 0) {
            return 0;
        }

        int count = Integer.MAX_VALUE;

        for (int i = 0; i < nums.length; i++) {
            int sum = nums[i];
            for (int j = i+1; j < nums.length; j++) {

                if (sum >= target) {
                    count = Math.min(count, j - i);
                }

                sum = sum + nums[j];
                if (sum >= target) {
                    count = Math.min(count, j - i + 1);
                    break;
                }

            }


        }


        return count;

    }


    public static void main(String[] args) {

        System.out.println(minSubArrayLen(7, new int[]{2, 3, 1, 2, 4, 3}));

    }


}
